/**
 * @Author ZhangCuirong
 * @Date 2025/9/18 10:09
 * @description:
 */
public class Solution493 {
    int[] temp;
    int[] counts;//用于记录每个元素右侧小于它的个数
    int[] indexes;//用于记录元素的原始索引，用于跟踪位置

    public int reversePairs(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        temp = new int[nums.length];
        counts = new int[nums.length];
        indexes = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            indexes[i] = i;
        }
        mergeSort(nums, 0, nums.length - 1);
        int count = 0;
        for (int i = 0; i < counts.length; i++) {
            count += counts[i];
        }
        return count;
    }

    public void mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, mid + 1, right);
    }

    public void merge(int[] nums, int l1, int r1, int l2, int r2) {
        if (l1 > r1 || l2 > r2) {
            return;
        }
        // 先统计翻转对数量
        int p1 = l1;
        int p2 = l2;


        // 统计阶段：计算左半部分与右半部分的翻转对
        for (p1 = l1; p1 <= r1; p1++) {
            // 移动 p2 直到找到第一个不满足 nums[i] > 2 * nums[j] 的 j
            while (p2 <= r2 && (long) nums[indexes[p1]] > 2L * nums[indexes[p2]]) {
                p2++;
            }
            counts[indexes[p1]] += p2 - l2;
        }
        // 归并阶段：合并两个有序数组
        p1 = l1;
        p2 = l2;
        int index = l1;
        while (p1 <= r1 && p2 <= r2) {
            if (nums[indexes[p1]] <= nums[indexes[p2]]) {//小于等于的时候判断，如果大于的时候判断会重复
                temp[index++] = indexes[p1++];
            } else {
                temp[index++] = indexes[p2++];
            }
        }
        while (p1 <= r1) {
            temp[index++] = indexes[p1++];
        }
        while (p2 <= r2) {
            temp[index++] = indexes[p2++];
        }
        for (int i = l1; i <= r2; i++) {
            indexes[i] = temp[i];
        }
    }

    public static void main(String[] args) {
        Solution493 solution = new Solution493();
        System.out.println(solution.reversePairs(new int[]{1, 3, 2, 3, 1}));
        System.out.println(solution.reversePairs(new int[]{2, 4, 3, 5, 1}));
    }
}
